class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> word_dict;
        for(auto it: wordDict){
            word_dict.insert(it);
        }

        vector<int> memo(word_dict.size()+1, 0);
        memo[0] = 1;
        for(int i=1; i<=s.size(); i++){
            for(int j=0; j<i; j++){
                if(memo[j] && word_dict.count(s.substr(j, i-j))){
                    memo[i] = 1;
                    break;
                }
            }
        }

        return memo.back();

    }
};